package _interview150;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 3. 无重复字符的最长子串
 */
public class No3 {
    private String s;

    /**
     * 1. 双指针
     */
    public int lengthOfLongestSubstring1(String s) {
        this.s = s;
        int start = 0, end = -1;
        int ans = 0;
        while (end < s.length() - 1) {
            end++;
            while (!isValid(start, end)) {
                start++;
            }
            ans = Math.max(end - start + 1, ans);
        }
        return ans;
    }

    private boolean isValid(int start, int end) {
        String substring = s.substring(start, end + 1);
        Set<Character> set = new HashSet<>();
        for (char c : substring.toCharArray()) {
            if (set.contains(c)) return false;
            set.add(c);
        }
        return true;
    }

    /**
     * 2. 双指针+哈希表
     */
    public int lengthOfLongestSubstring2(String s) {
        int start = 0, end = -1;
        Map<Character, Integer> map = new HashMap<>();
        int ans = 0;
        while (end < s.length() - 1) {
            end++;
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                start = Math.max(map.get(c) + 1, start);
            }
            map.put(c, end);
            ans = Math.max(end - start + 1, ans);
        }
        return ans;
    }
}
